# This file is part of Sonedyan.
#
# Sonedyan is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public
# License as published by the Free Software Foundation;
# either version 3 of the License, or (at your option) any
# later version.
#
# Sonedyan is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied
# warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
# PURPOSE.  See the GNU General Public License for more
# details.
#
# You should have received a copy of the GNU General Public.
# If not, see <http://www.gnu.org/licenses/>.
#
# Copyright (C) 2009-2012 Jimmy Dubuisson <jimmy.dubuisson@gmail.com>

library(igraph)
library(hash)

# get neighbours of specified node
get.neighbours <- function(g, i, m)
{
  V(g)[nei(V(g)[i], m)]
}

# get set of cycle path of length 'l' passing through vertex 'v'
get.vertex.cycles <- function(g, v, l)
{
	nv <- get.neighbours(g, v, "in")
	sp <- get.all.shortest.paths(g, v, nv, mode = "out")
	s <- sapply(sp, length)
	# return paths whose length equals l
	sp[which(s == l)]
}

# get set of unlabeled edge indexes
get.unlabeled.edge.indexes <- function(g, eids)
{
	h <- hash(eids, 0:(length(eids) - 1))
	reids <- c()

	for (u in E(g)$id)
	{
		if (!has.key(u, h))
		{	 
			reids <- append(reids, u)
		}
	}

	E(g)[E(g)$id %in% reids]
}

# args[3] -> <max-cycle-length>
#args <- commandArgs()
#n <- args[3]

core <- read.graph(file = "core-graphml.xml", format = "graphml")

# get cycles of length 'l'
get.cycles <- function(core, l)
{
	cycles <- c()
	eids <- c()
	vertices <- c()

	for (v in V(core))
	{
		cs <- get.vertex.cycles(core, v, l)
	
        	if (length(cs) > 0)
		{
			for (c in c(1:length(cs)))
			{
				cycle <- cs[[c]]
				
				cycle <- sort(cycle)
				cycle.id <- paste(cycle, collapse = ".")
				cycles <- unique(append(cycles, cycle.id))

				vertices <- unique(append(vertices, cycle))
			
				# complete vector of nodes with starting node
				cycle <- append(cycle, cycle[1])

				for (i in c(1:(length(cycle) - 1)))
				{
					edge <- paste(V(core)[cycle[i]]$name, "|", V(core)[cycle[i + 1]]$name, sep = "")
					eids <- unique(append(eids, edge))
				}
			}
		}
	}

	print(paste("# vertices ", l, ":", length(vertices)))
	print(paste("# edges ", l, ":", length(eids)))
	print(paste("# cycles ", l, ":", length(cycles)))

	list(v = vertices, e = eids)
}

# 2 cycles
cycles2 <- get.cycles(core, 2)

# 3 cycles
cycles3 <- get.cycles(core, 3)

# 4 cycles
cycles4 <- get.cycles(core, 4)

# 5 cycles
cycles5 <- get.cycles(core, 5)

# 6 cycles
cycles6 <- get.cycles(core, 6)

# 7 cycles
cycles7 <- get.cycles(core, 7)

# 8 cycles
cycles8 <- get.cycles(core, 8)

# 9 cycles
cycles9 <- get.cycles(core, 9)

# 10 cycles
cycles10 <- get.cycles(core, 10)

# 11 cycles
cycles11 <- get.cycles(core, 11)

# 12 cycles
cycles12 <- get.cycles(core, 12)

# 13 cycles
cycles13 <- get.cycles(core, 13)

# 14 cycles
cycles14 <- get.cycles(core, 14)

# 15 cycles
cycles15 <- get.cycles(core, 15)

# subgraph of union
# 2+3
#vertices <- union(cycles2$v, cycles3$v)
# 2+5
#vertices <- union(cycles2$v, cycles5$v)
# 2+3+4
#vertices <- union(cycles2$v, cycles3$v)
#vertices <- union(vertices, cycles4$v)
# 2+3+4+5
#vertices <- union(cycles2$v, cycles3$v)
#vertices <- union(vertices, cycles4$v)
#vertices <- union(vertices, cycles5$v)
# 2+3+4+5+6
#vertices <- union(cycles2$v, cycles3$v)
#vertices <- union(vertices, cycles4$v)
#vertices <- union(vertices, cycles5$v)
#vertices <- union(vertices, cycles6$v)
# 2+3+4+5+6+7
#vertices <- union(cycles2$v, cycles3$v)
#vertices <- union(vertices, cycles4$v)
#vertices <- union(vertices, cycles5$v)
#vertices <- union(vertices, cycles6$v)
#vertices <- union(vertices, cycles7$v)
# 2+3+4+5+6+7+8
#vertices <- union(cycles2$v, cycles3$v)
#vertices <- union(vertices, cycles4$v)
#vertices <- union(vertices, cycles5$v)
#vertices <- union(vertices, cycles6$v)
#vertices <- union(vertices, cycles7$v)
#vertices <- union(vertices, cycles8$v)
# 2+3+4+5+6+7+8+9
#vertices <- union(cycles2$v, cycles3$v)
#vertices <- union(vertices, cycles4$v)
#vertices <- union(vertices, cycles5$v)
#vertices <- union(vertices, cycles6$v)
#vertices <- union(vertices, cycles7$v)
#vertices <- union(vertices, cycles8$v)
#vertices <- union(vertices, cycles9$v)
# 2+3+4+5+6+7+8+9+10
#vertices <- union(cycles2$v, cycles3$v)
#vertices <- union(vertices, cycles4$v)
#vertices <- union(vertices, cycles5$v)
#vertices <- union(vertices, cycles6$v)
#vertices <- union(vertices, cycles7$v)
#vertices <- union(vertices, cycles8$v)
#vertices <- union(vertices, cycles9$v)
#vertices <- union(vertices, cycles10$v)
# 2+3+4+5+6+7+8+9+10+11
#vertices <- union(cycles2$v, cycles3$v)
#vertices <- union(vertices, cycles4$v)
#vertices <- union(vertices, cycles5$v)
#vertices <- union(vertices, cycles6$v)
#vertices <- union(vertices, cycles7$v)
#vertices <- union(vertices, cycles8$v)
#vertices <- union(vertices, cycles9$v)
#vertices <- union(vertices, cycles10$v)
#vertices <- union(vertices, cycles11$v)
# 2+3+4+5+6+7+8+9+10+11+12
#vertices <- union(cycles2$v, cycles3$v)
#vertices <- union(vertices, cycles4$v)
#vertices <- union(vertices, cycles5$v)
#vertices <- union(vertices, cycles6$v)
#vertices <- union(vertices, cycles7$v)
#vertices <- union(vertices, cycles8$v)
#vertices <- union(vertices, cycles9$v)
#vertices <- union(vertices, cycles10$v)
#vertices <- union(vertices, cycles11$v)
#vertices <- union(vertices, cycles12$v)
# 2+3+4+5+6+7+8+9+10+11+12+13
#vertices <- union(cycles2$v, cycles3$v)
#vertices <- union(vertices, cycles4$v)
#vertices <- union(vertices, cycles5$v)
#vertices <- union(vertices, cycles6$v)
#vertices <- union(vertices, cycles7$v)
#vertices <- union(vertices, cycles8$v)
#vertices <- union(vertices, cycles9$v)
#vertices <- union(vertices, cycles10$v)
#vertices <- union(vertices, cycles11$v)
#vertices <- union(vertices, cycles12$v)
#vertices <- union(vertices, cycles13$v)
# 2+3+4+5+6+7+8+9+10+11+12+13+14
#vertices <- union(cycles2$v, cycles3$v)
#vertices <- union(vertices, cycles4$v)
#vertices <- union(vertices, cycles5$v)
#vertices <- union(vertices, cycles6$v)
#vertices <- union(vertices, cycles7$v)
#vertices <- union(vertices, cycles8$v)
#vertices <- union(vertices, cycles9$v)
#vertices <- union(vertices, cycles10$v)
#vertices <- union(vertices, cycles11$v)
#vertices <- union(vertices, cycles12$v)
#vertices <- union(vertices, cycles13$v)
#vertices <- union(vertices, cycles14$v)
# 2+3+4+5+6+7+8+9+10+11+12+13+14+15
vertices <- union(cycles2$v, cycles3$v)
vertices <- union(vertices, cycles4$v)
vertices <- union(vertices, cycles5$v)
vertices <- union(vertices, cycles6$v)
vertices <- union(vertices, cycles7$v)
vertices <- union(vertices, cycles8$v)
vertices <- union(vertices, cycles9$v)
vertices <- union(vertices, cycles10$v)
vertices <- union(vertices, cycles11$v)
vertices <- union(vertices, cycles12$v)
vertices <- union(vertices, cycles13$v)
vertices <- union(vertices, cycles14$v)
vertices <- union(vertices, cycles15$v)

print(paste("# vertices (union):", length(vertices)))

sub <- subgraph(core, vertices)

print(paste("# subgraph vertices:", length(V(sub))))
print(paste("# subgraph edges:", length(E(sub))))

# intersection of edges
reis2 <- get.unlabeled.edge.indexes(sub, cycles2$e)
reis3 <- get.unlabeled.edge.indexes(sub, cycles3$e)
reis4 <- get.unlabeled.edge.indexes(sub, cycles4$e)
reis5 <- get.unlabeled.edge.indexes(sub, cycles5$e)
reis6 <- get.unlabeled.edge.indexes(sub, cycles6$e)
reis7 <- get.unlabeled.edge.indexes(sub, cycles7$e)
reis8 <- get.unlabeled.edge.indexes(sub, cycles8$e)
reis9 <- get.unlabeled.edge.indexes(sub, cycles9$e)
reis10 <- get.unlabeled.edge.indexes(sub, cycles10$e)
reis11 <- get.unlabeled.edge.indexes(sub, cycles11$e)
reis12 <- get.unlabeled.edge.indexes(sub, cycles12$e)
reis13 <- get.unlabeled.edge.indexes(sub, cycles13$e)
reis14 <- get.unlabeled.edge.indexes(sub, cycles14$e)
reis15 <- get.unlabeled.edge.indexes(sub, cycles15$e)

# 2+3
#reis <- intersect(reis2, reis3)
# 2+5
#reis <- intersect(reis2, reis5)
# 2+3+4
#reis <- intersect(reis2, reis3)
#reis <- intersect(reis, reis4)
# 2+3+4+5
#reis <- intersect(reis2, reis3)
#reis <- intersect(reis, reis4)
#reis <- intersect(reis, reis5)
# 2+3+4+5+6
#reis <- intersect(reis2, reis3)
#reis <- intersect(reis, reis4)
#reis <- intersect(reis, reis5)
#reis <- intersect(reis, reis6)
# 2+3+4+5+6+7
#reis <- intersect(reis2, reis3)
#reis <- intersect(reis, reis4)
#reis <- intersect(reis, reis5)
#reis <- intersect(reis, reis6)
#reis <- intersect(reis, reis7)
# 2+3+4+5+6+7+8
#reis <- intersect(reis2, reis3)
#reis <- intersect(reis, reis4)
#reis <- intersect(reis, reis5)
#reis <- intersect(reis, reis6)
#reis <- intersect(reis, reis7)
#reis <- intersect(reis, reis8)
# 2+3+4+5+6+7+8+9
#reis <- intersect(reis2, reis3)
#reis <- intersect(reis, reis4)
#reis <- intersect(reis, reis5)
#reis <- intersect(reis, reis6)
#reis <- intersect(reis, reis7)
#reis <- intersect(reis, reis8)
#reis <- intersect(reis, reis9)
# 2+3+4+5+6+7+8+9+10
#reis <- intersect(reis2, reis3)
#reis <- intersect(reis, reis4)
#reis <- intersect(reis, reis5)
#reis <- intersect(reis, reis6)
#reis <- intersect(reis, reis7)
#reis <- intersect(reis, reis8)
#reis <- intersect(reis, reis9)
#reis <- intersect(reis, reis10)
# 2+3+4+5+6+7+8+9+10+11
#reis <- intersect(reis2, reis3)
#reis <- intersect(reis, reis4)
#reis <- intersect(reis, reis5)
#reis <- intersect(reis, reis6)
#reis <- intersect(reis, reis7)
#reis <- intersect(reis, reis8)
#reis <- intersect(reis, reis9)
#reis <- intersect(reis, reis10)
#reis <- intersect(reis, reis11)
# 2+3+4+5+6+7+8+9+10+11+12
#reis <- intersect(reis2, reis3)
#reis <- intersect(reis, reis4)
#reis <- intersect(reis, reis5)
#reis <- intersect(reis, reis6)
#reis <- intersect(reis, reis7)
#reis <- intersect(reis, reis8)
#reis <- intersect(reis, reis9)
#reis <- intersect(reis, reis10)
#reis <- intersect(reis, reis11)
#reis <- intersect(reis, reis12)
# 2+3+4+5+6+7+8+9+10+11+12+13
#reis <- intersect(reis2, reis3)
#reis <- intersect(reis, reis4)
#reis <- intersect(reis, reis5)
#reis <- intersect(reis, reis6)
#reis <- intersect(reis, reis7)
#reis <- intersect(reis, reis8)
#reis <- intersect(reis, reis9)
#reis <- intersect(reis, reis10)
#reis <- intersect(reis, reis11)
#reis <- intersect(reis, reis12)
#reis <- intersect(reis, reis13)
# 2+3+4+5+6+7+8+9+10+11+12+13+14
#reis <- intersect(reis2, reis3)
#reis <- intersect(reis, reis4)
#reis <- intersect(reis, reis5)
#reis <- intersect(reis, reis6)
#reis <- intersect(reis, reis7)
#reis <- intersect(reis, reis8)
#reis <- intersect(reis, reis9)
#reis <- intersect(reis, reis10)
#reis <- intersect(reis, reis11)
#reis <- intersect(reis, reis12)
#reis <- intersect(reis, reis13)
#reis <- intersect(reis, reis14)
# 2+3+4+5+6+7+8+9+10+11+12+13+14+15
reis <- intersect(reis2, reis3)
reis <- intersect(reis, reis4)
reis <- intersect(reis, reis5)
reis <- intersect(reis, reis6)
reis <- intersect(reis, reis7)
reis <- intersect(reis, reis8)
reis <- intersect(reis, reis9)
reis <- intersect(reis, reis10)
reis <- intersect(reis, reis11)
reis <- intersect(reis, reis12)
reis <- intersect(reis, reis13)
reis <- intersect(reis, reis14)
reis <- intersect(reis, reis15)

# removing unlabeled edges
sub2 <- delete.edges(sub, reis)

print(paste("# new subgraph vertices:", length(V(sub2))))
print(paste("# new subgraph edges:", length(E(sub2))))

write.graph(sub2, file= "subgraph-gml-2+3+4+5+6+7+8+9+10+11+12+13+14+15-cycles.gml", format = "gml")
